package ua.mykola.backtracking;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class AllPermutations extends Backtrack {

	public void generate(int n) {
		backtrack(new int[n], 0, n);
	}

	@Override
	void processSolution(int[] a, int k) {
		System.out.println(Arrays.toString(a));

	}

	@Override
	boolean isSolution(int[] a, int k, int input) {
		return k == input;
	}

	@Override
	int[] constructCandidates(int[] a, int k, int input) {
		List<Integer> candidates = new LinkedList<Integer>();

		int NMAX = 100;

		boolean[] in_perm = new boolean[NMAX]; /* who is in the permutation? */
		for (int i = 1; i < NMAX; i++)
			in_perm[i] = false;
		for (int i = 0; i < k - 1; i++)
			in_perm[a[i]] = true;

		for (int i = 1; i <= input; i++)
			if (in_perm[i] == false) {
				candidates.add(i);
			}
		int[] candidatesArray = new int[candidates.size()];
		for (int i = 0; i < candidates.size(); i++) {
			candidatesArray[i] = candidates.get(candidates.size() - i - 1);
		}

		return candidatesArray;
	}
}
